Convolution techniques are used for a variety of image processing purposes. For two-dimensional images, convolution is employed for machine vision, pattern recognition, edge detection, edge enhancement by unsharp masking, spatial frequency filtering, and even deconvolution of images degraded by various aberrations produced in the image formation process. However, enthusiasm for convolutional techniques in image processing has been dampened by the fact that convolutions with large kernels on conventional sequential data processors is computationally expensive. The use of large kernels has therefore usually been restricted to applications in which speed of execution is not a major constraint.
Parallel data processing techniques could in principle relieve the execution time constraint of the convolution approach. Of primary concern in the development of parallel architectures for image processing is the efficient use of low-level, logical and arithmetic processes. By identifying and massively using such processes, processor architecture can be optimized for the most efficient execution, and high throughput rates can be achieved. In one frequently described approach, a separate elementary processor is assigned to each image element (i.e., pixel) in a two-dimensional image array, and data available to each processor is limited such that the operations performed by the processor depend on input data received from processors in a restricted local neighborhood. In a familiar rectangular scan format, a particular image pixel and its associated processor may be considered to have four neighbors, those to the north, south, east and west. Examples of parallel processors using this architecture are the DAP and MPP architectures. Alternatively, access may be granted to data from pixels along the diagonals as well, resulting in an eight-neighbor architecture such as the ClipIV architecture. Finally, six-neighbor architecture may result from hexagonal scan formats such as the diff3 scan format. However these architectures are limited to convolutions with 3.times.3 kernels, and therefore cannot directly operate with the large kernels that are required by general image processing. For example, such architectures cannot perform mean filtering or matched filtering over large support regions. This limitation has stimulated new approaches of dealing with large kernel requirements, utilizing small kernel architecture and multi-pass processing.
A paper entitled Design of Two-Dimensional FIR Filters From "Small" Generating Kernels, J. F. Abramatic and O. D. Saugeras, Proceedings IEEE Conference on Pattern Recognition and Image Processing, Chicago, Ill., May 1978, described a technique for decomposing a large kernel into the sequential application of 3.times.3 kernels. The Abramatic/Saugeras technique has come to be referred to as the small generating kernel (SGK) method. Subsequently, a simpler method of using the SGK technique was found by Pratt, and is set forth in U.S. Pat. No. 4,330,833. However, a drawback of the SGK method is that it requires complex and lengthy off-line calculations as a preliminary step in providing constants for the look-up tables used in the implementation. This involves a singular value decomposition of the large kernel, which necessitates a calculation of the eigenvalues of the product of the kernel and its transpose.